package com.dmall.sort.algorithm;

/**
 * 堆排序算法
 *
 * heapify的过程就是把任意的一个数组看成是一个堆，然后从最后一个非叶子节点开始到根节点（索引为0的节点）执行shiftDown操作
 * 对于如何拿到最后一个非叶子节点的索引呢？很简单，其实就是最后一个节点(arr.length - 1)的父节点(arr.length - 2) / 2
 *
 * heapify的过程的时间复杂度是O(n)，但是如果将n个元素逐个插入到空堆中，时间复杂度为O(nlogn) 有n个数，每个shiftUp都是logn，索引总的来说是O(nlogn)
 * @author xiao1.wang
 * @date 2021-10-08 18:12:54
 */
@SuppressWarnings("all")
public class HeapSort implements Sort {

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        heapify(arr);
        heapSort(arr);
    }

    private void heapSort(int[] arr) {
        for (int i = arr.length - 1; i >= 0; i--) {
            // 堆顶元素（数组的最大值）和最后索引的元素进行交换（相当于是将最大值放到了数组的最后）
            swap(arr, 0, i);
            // 堆顶元素不是最大值了，需要执行shiftDown操作
            shiftDown(arr, 0, i);
        }
    }

    private void heapify(int[] arr) {
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            shiftDown(arr, i, arr.length);
        }
    }

    /**
     * 对 arr[0, n) 所形成的最大堆中，索引 index 的元素，执行shiftDown
     * @param arr 数组
     * @param index 索引
     * @param n 前面多少个元素形成最大堆
     */
    private void shiftDown(int[] arr, int index, int n) {
        while (2 * index + 1 < n) {
            int maxIndex = 2 * index + 1;
            if (maxIndex + 1 < n && arr[maxIndex] < arr[maxIndex + 1]) {
                maxIndex ++;
            }
            if (arr[index] >= arr[maxIndex]) {
                break;
            }
            swap(arr, index, maxIndex);
            index = maxIndex;
        }
    }

    @Override
    public String getName() {
        return "堆排序";
    }

    public static void main(String[] args) {
        int[] arr = {6, 9, 4, 7, 2, 8, 3, 1, 10, 5};
        Sort.printArr(arr);
        Sort sort = new HeapSort();
        sort.sort(arr);
        Sort.printArr(arr);
    }
}
